/*
 *  Quick sort
 */
package algs4.sort;

public class Quick
{
    /* Static Methods */
    public static void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

    public static void sort(Comparable[] a, int st, int ed) {
        // base case
        if (ed <= st) return;

        int k = partition(a, st, ed);

        sort(a, st, k - 1);
        sort(a, k + 1, ed);
    }

    private static int partition(Comparable[] a, int st, int ed) {
        int i = st;
        int j = ed;

        Comparable v = a[i];

        while (i < j) {
            while (i < j && a[j].compareTo(v) >= 0) j--;
            a[i] = a[j];

            while (i < j && a[i].compareTo(v) <= 0) i++;
            a[j] = a[i];
        }

        // retrieve
        a[i] = v;

        return i;
    }

    /* version of Algorithms 4 */
    /* private static int partition(Comparable[] a, int st, int ed) {
        int i = st;
        int j = ed + 1;

        Comparable v = a[i];

        while (true) {
            while (a[++i].compareTo(v) < 0) {
                if (i == ed) break;
            }

            while (a[--j].compareTo(v) > 0) {
                if (j == st) break;
            }

            if (i >= j) break;

            exch(a, i, j);
        }

        exch(a, st, j);

        return j;
    } */

    private static void exch(Object[] a, int p, int q) {
        Object v = a[p];

        a[p] = a[q];
        a[q] = v;
    }
}
